\begin{equation} \| \nabla f(x_k)\|_2 < 10^{-8} \\ \| p_k \|_2 < 10^{-4}\\ \| x_{k-1}-x_k\|_2 < 10^{-5} \|x_{k-1}\|_2 \\ n_{iter}> 249 \end{equation}
resn, pathn = busqueda_linea(rosen, np.array([2,2]), direction='newton')
resm, pathm = busqueda_linea(rosen, np.array([2,2]), direction='max')
plot_path(0, 3, -2, 5, lambda x,y: 100*(y-x**2)**2+(x-1)**2, [1,1], pathn, pathm)
Converge bien en Newton (16 iteraciones) pero no en máximo descenso:
comparar(rosen, [2,2], 'newton', 0)
Método hibrido
16 iteraciones (puntos pisados)
18 iteraciones totales para encontrar alpha
Error absoluto: 1.9020312854274676e-22
Norma del gradiente: 5.797926033700089e-10
¿Hessiana definida positiva?: True
Método backtracking
15 iteraciones (puntos pisados)
20 iteraciones totales para encontrar alpha
Error absoluto: 1.0706814636112183e-27
Norma del gradiente: 2.5820771894751094e-13
¿Hessiana definida positiva?: True
Método interpol
29 iteraciones (puntos pisados)
47 iteraciones totales para encontrar alpha
Error absoluto: 0.0
Norma del gradiente: 0.0
¿Hessiana definida positiva?: True
comparar(rosen, [2,2], 'max', 0)
Método hibrido
1 iteraciones (puntos pisados)
2 iteraciones totales para encontrar alpha
Error absoluto: 400.97718761859034
Norma del gradiente: 1651.125202276957
¿Hessiana definida positiva?: True
Método backtracking
250 iteraciones (puntos pisados)
2734 iteraciones totales para encontrar alpha
Error absoluto: 0.5024870441274595
Norma del gradiente: 0.4741193290903157
¿Hessiana definida positiva?: True
Método interpol
1 iteraciones (puntos pisados)
2 iteraciones totales para encontrar alpha
Error absoluto: 400.9943271014148
Norma del gradiente: 1651.1683315314112
¿Hessiana definida positiva?: True
resn, pathn = busqueda_linea(rastrigin, np.array([0.4, 0.3]), direction='newton')
resm, pathm = busqueda_linea(rastrigin, np.array([0.4, 0.3]), direction='max')
plot_path(-4, 4, -4, 4, lambda x,y: 20+x**2+y**2-10*np.cos(2*np.pi*x)-10*np.cos(2*np.pi*y), [0,0], pathn, pathm)
Se va a mínimos locales en ambos casos, pero igual es mejor el de máximo descenso.
comparar(rastrigin, [0.4, 0.3], 'max', 0)
Método hibrido
15 iteraciones (puntos pisados)
93 iteraciones totales para encontrar alpha
Error absoluto: 9.949560298682503
Norma del gradiente: 0.0002847154495140465
¿Hessiana definida positiva?: True
Método backtracking
19 iteraciones (puntos pisados)
165 iteraciones totales para encontrar alpha
Error absoluto: 7.959662391640073
Norma del gradiente: 0.0028880936340078336
¿Hessiana definida positiva?: True
Método interpol
8 iteraciones (puntos pisados)
32 iteraciones totales para encontrar alpha
Error absoluto: 7.959662381108178
Norma del gradiente: 5.886626313876674e-07
¿Hessiana definida positiva?: True
comparar(rastrigin, [0.4, 0.3], 'newton', 0)
Método hibrido
5 iteraciones (puntos pisados)
5 iteraciones totales para encontrar alpha
Error absoluto: 21.246232048083407
Norma del gradiente: 2.0758067189737618e-12
¿Hessiana definida positiva?: False
Método backtracking
5 iteraciones (puntos pisados)
6 iteraciones totales para encontrar alpha
Error absoluto: 21.246232048083407
Norma del gradiente: 2.0758067189737618e-12
¿Hessiana definida positiva?: False
Método interpol
4 iteraciones (puntos pisados)
45 iteraciones totales para encontrar alpha
Error absoluto: 21.246232048083407
Norma del gradiente: 1.4236912322732654e-09
¿Hessiana definida positiva?: False
resn, pathn = busqueda_linea(griewank, np.array([0.4, 0.3]), direction='newton')
resm, pathm = busqueda_linea(griewank, np.array([0.4, 0.3]), direction='max')
plot_path(-4, 4, -1, 1, lambda x,y: (x**2+y**2)/4000-np.cos(x)-np.cos(y/np.sqrt(2))+1, [0,0], pathn, pathm)
No converge al mínimo global.
comparar(griewank, [2,0], 'newton', 0)
Método hibrido
250 iteraciones (puntos pisados)
5000 iteraciones totales para encontrar alpha
Error absoluto: 1.9997657515249214
Norma del gradiente: 0.07345859762521041
¿Hessiana definida positiva?: False
Método backtracking
1 iteraciones (puntos pisados)
21 iteraciones totales para encontrar alpha
Error absoluto: 1.4171487378094147
Norma del gradiente: 0.910296558696437
¿Hessiana definida positiva?: False
Método interpol
3 iteraciones (puntos pisados)
63 iteraciones totales para encontrar alpha
Error absoluto: 2.0024686354182357
Norma del gradiente: 5.662764158903559e-12
¿Hessiana definida positiva?: False
comparar(griewank, [2,0], 'max', 0)
Método hibrido
5 iteraciones (puntos pisados)
5 iteraciones totales para encontrar alpha
Error absoluto: 0.0
Norma del gradiente: 3.207949331562903e-10
¿Hessiana definida positiva?: True
Método backtracking
5 iteraciones (puntos pisados)
5 iteraciones totales para encontrar alpha
Error absoluto: 0.0
Norma del gradiente: 3.207949331562903e-10
¿Hessiana definida positiva?: True
Método interpol
5 iteraciones (puntos pisados)
5 iteraciones totales para encontrar alpha
Error absoluto: 0.0
Norma del gradiente: 3.207949331562903e-10
¿Hessiana definida positiva?: True
resm, pathm = busqueda_linea(ackley, np.array([0, 1.5]), direction='max')
resn, pathn = busqueda_linea(ackley, np.array([0, 1.5]), direction='newton')
ack = lambda x,y: -20*np.exp(-0.2/2*(x**2+y**2))-np.exp(1/2*(np.cos(2*np.pi*x))+np.cos(2*np.pi*y))+20+np.exp(1)
plot_path(-1, 1, -2, 2, ack, [0,0], pathn, pathm)
Converge en máximo descenso pero no en Newton.
comparar(ackley, [0, 1.5], 'max', 0)
Método hibrido
250 iteraciones (puntos pisados)
596 iteraciones totales para encontrar alpha
Error absoluto: 7.991167733978344e-05
Norma del gradiente: 0.0010731414684836292
¿Hessiana definida positiva?: True
Método backtracking
14 iteraciones (puntos pisados)
84 iteraciones totales para encontrar alpha
Error absoluto: 4.8874380542685e-08
Norma del gradiente: 6.565128451534153e-07
¿Hessiana definida positiva?: True
Método interpol
250 iteraciones (puntos pisados)
508 iteraciones totales para encontrar alpha
Error absoluto: 4.094411112776086e-05
Norma del gradiente: 0.0005499136182511599
¿Hessiana definida positiva?: True
comparar(ackley, [0, 1.5], 'newton', 0)
Método hibrido
250 iteraciones (puntos pisados)
5000 iteraciones totales para encontrar alpha
Error absoluto: 5.668459570618797
Norma del gradiente: 0.1853727347721762
¿Hessiana definida positiva?: False
Método backtracking
1 iteraciones (puntos pisados)
21 iteraciones totales para encontrar alpha
Error absoluto: 5.541124207560927
Norma del gradiente: 2.287793424185262
¿Hessiana definida positiva?: False
Método interpol
3 iteraciones (puntos pisados)
63 iteraciones totales para encontrar alpha
Error absoluto: 5.669249530986374
Norma del gradiente: 1.2754842080140425e-09
¿Hessiana definida positiva?: False
resn, pathn = busqueda_linea(branin, np.array([-4, 13]), direction='newton')
resm, pathm = busqueda_linea(branin, np.array([-4, 13]), direction='max')
bran = lambda x,y: (y-(5.1/(4*np.pi**2))*x**2+(5/np.pi)*x-6)**2 + 10*(1-(1/(8*np.pi)))*np.cos(x)+10
plot_path(-5, 5, 10, 15, bran, [-np.pi,12.275], pathn, pathm)
Converge al mínimo global en 62 iteraciones con máximo descenso y en 4 con Newton.
comparar(branin, [-4, 13], 'newton', 0.39789)
Método hibrido
4 iteraciones (puntos pisados)
4 iteraciones totales para encontrar alpha
Error absoluto: 2.642270261865587e-06
Norma del gradiente: 8.249413606590028e-15
¿Hessiana definida positiva?: True
Método backtracking
4 iteraciones (puntos pisados)
4 iteraciones totales para encontrar alpha
Error absoluto: 2.642270261865587e-06
Norma del gradiente: 8.249413606590028e-15
¿Hessiana definida positiva?: True
Método interpol
4 iteraciones (puntos pisados)
4 iteraciones totales para encontrar alpha
Error absoluto: 2.642270261865587e-06
Norma del gradiente: 8.249413606590028e-15
¿Hessiana definida positiva?: True
comparar(branin, [-4, 13], 'max', 0.39789)
Método hibrido
62 iteraciones (puntos pisados)
125 iteraciones totales para encontrar alpha
Error absoluto: 2.1708060093383885e-06
Norma del gradiente: 0.0011270208200181747
¿Hessiana definida positiva?: True
Método backtracking
73 iteraciones (puntos pisados)
324 iteraciones totales para encontrar alpha
Error absoluto: 2.3269942396875187e-06
Norma del gradiente: 0.0008911922620369977
¿Hessiana definida positiva?: True
Método interpol
69 iteraciones (puntos pisados)
139 iteraciones totales para encontrar alpha
Error absoluto: 2.1247442753558055e-06
Norma del gradiente: 0.0010567900571462794
¿Hessiana definida positiva?: True
resn, pathn = busqueda_linea(easom, np.array([5, 5]), direction='newton')
resm, pathm = busqueda_linea(easom, np.array([5, 5]), direction='max')
eas = lambda x,y: -np.cos(x)*np.cos(y)*np.exp(-(x-np.pi)**2-(y-np.pi)**2)
plot_path(2, 6, 2, 6, eas, [np.pi,np.pi], pathn, pathm)
En ambos casos se atora y casi no avanza.
comparar(easom, [5,5], 'max', -1)
Método hibrido
1 iteraciones (puntos pisados)
1 iteraciones totales para encontrar alpha
Error absoluto: 0.9999195021439116
Norma del gradiente: 3.824027924812036e-05
¿Hessiana definida positiva?: True
Método backtracking
1 iteraciones (puntos pisados)
1 iteraciones totales para encontrar alpha
Error absoluto: 0.9999195021439116
Norma del gradiente: 3.824027924812036e-05
¿Hessiana definida positiva?: True
Método interpol
1 iteraciones (puntos pisados)
1 iteraciones totales para encontrar alpha
Error absoluto: 0.9999195021439116
Norma del gradiente: 3.824027924812036e-05
¿Hessiana definida positiva?: True
comparar(easom, [5,5], 'newton', -1)
Método hibrido
3 iteraciones (puntos pisados)
3 iteraciones totales para encontrar alpha
Error absoluto: 0.9999188977610843
Norma del gradiente: 7.518022531585278e-13
¿Hessiana definida positiva?: True
Método backtracking
3 iteraciones (puntos pisados)
3 iteraciones totales para encontrar alpha
Error absoluto: 0.9999188977610843
Norma del gradiente: 7.518022531585278e-13
¿Hessiana definida positiva?: True
Método interpol
3 iteraciones (puntos pisados)
3 iteraciones totales para encontrar alpha
Error absoluto: 0.9999188977610843
Norma del gradiente: 7.518022531585278e-13
¿Hessiana definida positiva?: True
resn, pathn = busqueda_linea(second_schaffer, np.array([1, 1]), direction='newton')
resm, pathm = busqueda_linea(second_schaffer, np.array([1, 1]), direction='max')
sha2 = lambda x,y: 0.5 + (np.sin(x**2-y**2)**2-0.5)/(1+0.001*(x**2+y**2))**2
plot_path(-2, 2, -2, 2, sha2, [0,0], pathn, pathm)
Newton converge rápido (en 2 iteraciones) y máximo no converge.
comparar(second_schaffer, [1,1], 'newton', 0)
Método hibrido
2 iteraciones (puntos pisados)
2 iteraciones totales para encontrar alpha
Error absoluto: 0.0
Norma del gradiente: 6.041888845386573e-11
¿Hessiana definida positiva?: True
Método backtracking
2 iteraciones (puntos pisados)
2 iteraciones totales para encontrar alpha
Error absoluto: 0.0
Norma del gradiente: 6.041888845386573e-11
¿Hessiana definida positiva?: True
Método interpol
2 iteraciones (puntos pisados)
2 iteraciones totales para encontrar alpha
Error absoluto: 0.0
Norma del gradiente: 6.041888845386573e-11
¿Hessiana definida positiva?: True
comparar(second_schaffer, [1,1], 'max', 0)
Método hibrido
250 iteraciones (puntos pisados)
250 iteraciones totales para encontrar alpha
Error absoluto: 0.0007370074220333089
Norma del gradiente: 0.0017141357166399614
¿Hessiana definida positiva?: True
Método backtracking
250 iteraciones (puntos pisados)
250 iteraciones totales para encontrar alpha
Error absoluto: 0.0007370074220333089
Norma del gradiente: 0.0017141357166399614
¿Hessiana definida positiva?: True
Método interpol
250 iteraciones (puntos pisados)
250 iteraciones totales para encontrar alpha
Error absoluto: 0.0007370074220333089
Norma del gradiente: 0.0017141357166399614
¿Hessiana definida positiva?: True
resn, pathn = busqueda_linea(shubert, np.array([3, 1]), direction='newton')
resm, pathm = busqueda_linea(shubert, np.array([3, 1]), direction='max')
def shub(x,y):
resx = resy = 0
for i in range(1,6):
resx += i*np.cos((i+1)*x+i)
resy += i*np.cos((i+1)*y+i)
return resx*resy
plot_path(0, 45, 0, 6, shub, [36.27,5.48], pathn, pathm)
En máximo descenso converge al mínimo global, en Newton a un local.
comparar(shubert, [1,2], 'max', -186.7309)
Método hibrido
61 iteraciones (puntos pisados)
580 iteraciones totales para encontrar alpha
Error absoluto: 0.003339219275119376
Norma del gradiente: 5.584063730986149
¿Hessiana definida positiva?: True
Método backtracking
12 iteraciones (puntos pisados)
113 iteraciones totales para encontrar alpha
Error absoluto: 7.118507454606515e-06
Norma del gradiente: 0.12506160293912852
¿Hessiana definida positiva?: True
Método interpol
11 iteraciones (puntos pisados)
50 iteraciones totales para encontrar alpha
Error absoluto: 140.2195857670354
Norma del gradiente: 0.01015741489901536
¿Hessiana definida positiva?: True
comparar(shubert, [1,2], 'newton', -186.7309)
Método hibrido
4 iteraciones (puntos pisados)
4 iteraciones totales para encontrar alpha
Error absoluto: 186.7309
Norma del gradiente: 2.8731249840155636e-13
¿Hessiana definida positiva?: False
Método backtracking
4 iteraciones (puntos pisados)
4 iteraciones totales para encontrar alpha
Error absoluto: 186.7309
Norma del gradiente: 2.8731249840155636e-13
¿Hessiana definida positiva?: False
Método interpol
4 iteraciones (puntos pisados)
4 iteraciones totales para encontrar alpha
Error absoluto: 186.7309
Norma del gradiente: 2.8731249840155636e-13
¿Hessiana definida positiva?: False